package LeetCode刷题;

import java.util.LinkedList;

/**
 * @program: Java_Study
 * @author: Xiaofan
 * @createTime: 2021-10-02 19:52
 * @description: Functions of this class is
 *
 **/
public class No回文链表 {
    public static void main(String[] args) {

    }
    public static class ListNode {
      int val;
      ListNode next;
      ListNode() {}
      ListNode(int val) { this.val = val; }
      ListNode(int val, ListNode next) { this.val = val; this.next = next; }
  }
    public static boolean isPalindrome(ListNode head) {
        /**
         * 自我理解做法：
         * 快慢指针+反转部分链表
         *class Solution {
         *     public boolean isPalindrome(ListNode head) {
         *         if(head != null && head.next != null){
         *             //双指针+局部反转判断
         *             ListNode cur = head;
         *             ListNode pre = null;
         *             int len = 0;
         *             while(cur != null){
         *                 cur = cur.next;
         *                 len++;
         *             }
         *             if(len == 2){
         *                 return head.val == head.next.val;
         *             }
         *             cur = head;
         *             int sum = len/2;
         *             while(--sum >= 0){
         *                 ListNode temp = cur.next;
         *                 cur.next = pre;
         *                 pre = cur;
         *                 cur = temp;
         *             }
         *             //开始判断
         *
         *             if((len%2) != 0){
         *                 //奇数长度
         *                 cur = cur.next;
         *             }
         *             while(cur != null && pre != null){
         *                 if(cur.val != pre.val ){
         *                     return false;
         *                 }
         *                 cur = cur.next;
         *                 pre = pre.next;
         *             }
         *         }
         *         return true;
         *     }
         * }
         */
        if(head!=null){
            LinkedList<Integer> stack=new LinkedList();
            ListNode p=head;
            while(p!=null){
                stack.push(p.val);
                p=p.next;
            }
            while (head!=null){
                if(head.val!=stack.pop()){
                    return false;
                }
                head=head.next;
            }
            return true;
        }
        return false;
    }
}